package todo;

import graph.Hungary;

public class Dilworth {

	/**
	 * 
	 * @return max size of the antichains, which is also the min number of the
	 *         chains
	 */
	public int maxAntichain(boolean[][] dag, int n) {
		for (int k = 0; k < n; ++k)
			for (int i = 0; i < n; ++i)
				for (int j = 0; j < n; ++j)
					dag[i][j] = dag[i][j] || dag[i][k] && dag[k][j];
		Hungary bimatch = new Hungary();
		return n - bimatch.hungaryBFS(dag, n, n);
	}

}
